如前一章所示，解析器是从语法派生出来的。回顾一下所有的构造规则，对于语法的每个规则，创建一个以规则左侧的非终结符命名的方法来解析规则的右侧。根据右边的定义，可以有以下操作:

\begin{itemize}
\item
对于每个非终结符，调用相应的方法

\item
每个标记都要进行处理

\item
对于备选项和可选的或重复的组，将检查超前标记(下一个未使用的令牌)，以决定在何处继续
\end{itemize}

让我们将这些结构规则应用于以下语法规则:

\begin{shell}
ifStatement
    : "IF" expression "THEN" statementSequence
        ( "ELSE" statementSequence )? "END" ;
\end{shell}

可以很容易地将其转换为下面的C++代码:

\begin{cpp}
void Parser::parseIfStatement() {
    consume(tok::kw_IF);
    parseExpression();
    consume(tok::kw_THEN);
    parseStatementSequence();
    if (Tok.is(tok::kw_ELSE)) {
        advance();
        parseStatementSequence();
    }
    consume(tok::kw_END);
}
\end{cpp}

tinylang的整个语法可以通过这种方式转换成C++。因为在互联网上找到的大多数语法都不适合这种结构，所以必须小心避免一些陷阱。

\begin{myTip}{语法和解析器}
有两种不同类型的解析器:自顶向下解析器和自底向上解析器。其名称来源于解析过程中处理规则的顺序，解析器的输入是词法分析器生成的标记序列。

自顶向下解析器展开规则中最左边的符号，直到匹配到一个标记。若使用了所有标记并展开了所有符号，则解析成功。这正是tinylang解析器的工作方式。

自底而上的解析器则相反:查看标记序列，并尝试用规则左侧的语法符号替换这些标记。例如，接下来的标记是if、3、+和4，自下而上的解析器将用expression符号替换3 + 4标记，从而产生IF expression序列。当检测到一系列属于完整IF语句的标记时，这个标记和符号序列将使用ifStatement符号替换。

若使用了所有标记，并且只剩下开始符号，则解析成功。虽然自顶向下的解析器可以很容易地手工构造，但自底向上的解析器却不是这样。

描述这两种解析器的另一种方法是首先展开符号。两者都从左到右读取输入，但是自顶向下的解析器首先展开最左边的符号，而自底向上的解析器首先展开最右边的符号。因此，自顶向下的解析器也称为LL解析器，而自底向上的解析器称为LR解析器。

语法必须具有某些属性，才可以从中派生出LL或LR解析器。语法是相应地命名的:需要一个LL语法来构造LL解析器。

可以在大学教科书中找到有关编译器构造的更多细节，例如Wilhelm, Seidl和Hack合著的《Compiler Design. Syntactic and Semantic Analysis》，Springer 2013，以及Grune和Jacobs合著的《Parsing Techniques, A practical guide》，Springer 2008。
\end{myTip}

需要查找的一个问题是左递归规则。若规则的右侧以与左侧相同的终端开始，则称为左递归规则。典型的例子可以在表达式语法中看到:

\begin{shell}
expression : expression "+" term ;
\end{shell}

若从语法上看还不清楚，翻译成的C++会很明显地有无限递归:

\begin{cpp}
void Parser::parseExpression() {
    parseExpression();
    consume(tok::plus);
    parseTerm();
}
\end{cpp}

左递归也可以间接发生，并且涉及更多规则，这更难以发现。这就是为什么会存在一种可以检测和消除左递归的算法。

\begin{myNotic}{Note}
左递归规则只是LL解析器的问题，比如tinylang的递归下降解析器。原因是这些解析器首先展开最左边的符号。相反，若使用解析器生成器生成LR解析器，首先展开最右边的符号，则应该避免右递归规则。
\end{myNotic}

每一步中，解析器仅仅通过提前查看后续的标记来决定如何继续解析。若不能确定地做出这个决定，则代表语法有冲突。为了说明这一点，看一下C\#中的using语句。与C++一样，using语句可用于使符号在命名空间中可见，例如using Math;。也可以用using M = Math;为导入的符号定义别名。在语法中，这可以表示为:

\begin{shell}
usingStmt : "using" (ident "=")? ident ";"
\end{shell}

这里有一个问题:在解析器使用using关键字之后，预检标记是ident类型的，但这些信息不足以让我们决定是否跳过或解析中间的可选组。若可选组开始使用的标记集与可选组后面的标记集重叠，就会出现这种情况。

让我们用另一种不使用可选组的方法来重写这个规则:

\begin{shell}
usingStmt : "using" ( ident "=" ident | ident ) ";" ;
\end{shell}

现在，有一个不同的冲突:两种选择都以相同的标记开始。解析器只查看预检标记，无法确定哪个选项是正确的。

这些冲突很常见，知道如何处理它们就好。一种方法是以消除冲突的方式重写语法。在前面的示例中，两种备选方案都以相同的标记开头，我们可以把此标记提取出来，得到以下规则:

\begin{shell}
usingStmt : "using" ident ("=" ident)? ";" ;
\end{shell}

这种表述没有冲突，但也应该注意到它的表达不够直观。在另外两个公式中，很明显哪个标识是别名，哪个标识是命名空间名。在无冲突规则中，最左边的标识的角色可能会改变。一开始，它是命名空间的名称，但若后面跟着等号，它就变成了别名。

第二种方法是添加一个谓词来区分这两种情况。该谓词通常称为解析器(resolver)，可以使用上下文信息进行决策(例如在符号表中查找名称)，也可以查看多个标记。假设词法分析器有一个名为Token \&peek(int n)的方法，该方法在当前的超前标记之后返回第n个标记。这里，等号的存在性可以作为判断过程中的额外谓词:

\begin{cpp}
if (Tok.is(tok::ident) && Lex.peek(0).is(tok::equal)) {
    advance();
    consume(tok::equal);
}
consume(tok::ident);
\end{cpp}

第三种方法是使用回溯。为此，需要保存当前状态，并且尝试解析冲突的组。若这没有成功，需要返回到保存的状态并尝试另一个路径。这里搜索的是要应用的正确规则，效率不如其他方法。因此，只能在万不得已的情况下才会使用这种方法。

现在，让我们加入错误恢复。上一章中，介绍了一种称为恐慌模式(panic mode)的错误恢复技术。基本思想是跳过标记，直到找到一个适合继续解析的标记。例如，在tinylang中，语句后跟分号(:)。

若If语句中存在语法问题，则跳过所有标记，直到找到分号为止，再继续执行下一个语句。与其使用临时定义的标记集，不如使用系统的方法。

对于每个非终结符，计算可以跟在该非终结符后面的标记集合,称为跟随集(FOLLOW Set)。对于语句非终结符，后面可以是;、ELSE和END标记，所以必须在parseStatement()的错误恢复部分使用这个集。这个方法假定语法错误可以就地处理，但大多数情况下这是不可能的。解析器可能会跳过很多标记，直到到达输入的结尾。在这种情况下，无法进行就地恢复。

为了防止无意义的错误消息，需要通知调用方法错误恢复仍未完成。这可以通过bool来实现。若返回true，则表示错误恢复尚未完成，而false则表示解析(包括可能的错误恢复)成功。

有许多方法可以扩展此错误恢复方案。使用主动调用者的FOLLOW集合是一种常见的方法。作为一个简单的例子，假设parseStatement()由parseStatementSequence()调用，而parseBlock()本身又由parseModule()调用。

这里，每个相应的非终结符都有一个FOLLOW集合。若解析器在parseStatement()中检测到语法错误，则跳过标记，直到当前标记出现在至少一个主动调用者的FOLLOW集合中。若标记位于当前语句的FOLLOW集合中，则就地恢复错误，并向调用者返回false；否则，返回true，表示必须继续进行错误恢复。这个扩展的一种可能的实现策略是将std::bitset或std::tuple传递给调用方，以表示当前FOLLOW集合的并集。

最后一个问题仍然没有解决:我们如何调用错误恢复?上一章中，goto用于跳转到错误恢复块。这是可行的，但不够好。根据前面讨论的内容，我们可以在单独的方法中跳过标记。Clang有一个用于此目的的方法skipUntil()，tinylang也可以用。

因为下一步是向解析器添加语义操作，所以若有必要的话，最好有一个中央位置放置清理代码。嵌套函数将是理想的选择。C++没有嵌套函数，而Lambda函数可以达到类似的目的。我们最初看到的parseIfStatement()方法在添加完整的错误恢复代码时，类似如下实现:

\begin{cpp}
bool Parser::parseIfStatement() {
    auto _errorhandler = [this] {
        return skipUntil(tok::semi, tok::kw_ELSE, tok::kw_END);
    };
    if (consume(tok::kw_IF))
        return _errorhandler();
    if (parseExpression(E))
        return _errorhandler();
    if (consume(tok::kw_THEN))
        return _errorhandler();
    if (parseStatementSequence(IfStmts))
        return _errorhandler();
    if (Tok.is(tok::kw_ELSE)) {
        advance();
        if (parseStatementSequence(ElseStmts))
        return _errorhandler();
    }
    if (expect(tok::kw_END))
        return _errorhandler();
    return false;
}
\end{cpp}

\begin{myTip}{解析器和词法分析器生成器}
手动构造解析器和词法分析器可能是一项乏味的任务，特别是在尝试发明一种新的编程语言，并经常更改语法的情况下。幸运的是，有些工具可以自动完成这项任务。

经典的Linux工具是flex(\url{https://github.com/westes/flex})和bison (\url{https://www.gnu.org/software/bison/})。flex从一组正则表达式生成词法分析器，而bison从语法描述生成LALR(1)解析器。这两个工具都可以生成C/C++源代码，并且可以一起使用。

另一个流行的工具是AntLR(\url{https://www.antlr.org/})。AntLR可以从语法描述生成词法分析器、解析器和AST。生成的解析器属于LL(*)类，所以它是一个自顶向下的解析器，使用可变数量的提前查找量(lookahead)来解决冲突。该工具是用Java编写的，但可以生成许多流行语言的源代码，包括C/C++。

所有这些工具都需要一些库支持。若正在寻找生成自包含的词法分析器和解析器的工具，那么Coco/R(\url{https://ssw.jku.at/Research/Projects/Coco/})可能是适合您的工具。Coco/R根据LL(1)语法描述生成词法分析器和递归下降解析器，类似于本书中使用的语法描述。生成的文件基于模板文件，可以根据需要更改模板文件。该工具用C\#编写的，可以移植到C++、Java和其他语言。

还有许多其他可用的工具，其在特性和支持的输出语言方面差异很大。在选择工具时，也需要考虑权衡。LALR(1)解析器生成器(如bison)可以接受范围广泛的语法，可以在互联网上找到的免费语法通常是LALR(1)语法。

缺点是，这些生成器生成需要在运行时解释的状态机，这可能比递归下降解析器慢，错误处理也更加复杂。Bison对处理语法错误提供了基本支持，但要正确使用它，需要对解析器的工作原理有深入的了解。与此相比，AntLR消耗的语法类略小，但会自动生成错误处理，并且还可以生成AST，所以重写语法以便与AntLR一起使用可能会加快之后的开发进度。
\end{myTip}
